package dxcTopic;
import java.util.Arrays;

public class wuxuArr_Sort {

    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 9, 1, 3, 6, 4, 7};

        // 创建一个辅助数组用于归并
        int[] aux = new int[arr.length];

        // 创建线程数组
        Thread[] threads = new Thread[arr.length];

        // 创建子任务并分配给线程
        for (int i = 0; i < arr.length; i++) {
            int[] subArr = Arrays.copyOfRange(arr, i, i + 1);
            Runnable task = new MergeSortTask(subArr, aux);
            threads[i] = new Thread(task);
            threads[i].start();
        }

        // 等待所有线程执行完毕
        for (Thread thread : threads) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        // 使用多线程的归并操作合并子数组
        merge(arr, aux);

        // 输出排序后的结果
        System.out.println(Arrays.toString(arr));
    }

    private static void merge(int[] arr, int[] aux) {
        int mid = arr.length / 2;
        int i = 0, j = mid, k = 0;

        while (i < mid && j < arr.length) {
            if (arr[i] <= arr[j]) {
                aux[k++] = arr[i++];
            } else {
                aux[k++] = arr[j++];
            }
        }

        while (i < mid) {
            aux[k++] = arr[i++];
        }

        while (j < arr.length) {
            aux[k++] = arr[j++];
        }

        System.arraycopy(aux, 0, arr, 0, arr.length);
    }

    static class MergeSortTask implements Runnable {
        private final int[] arr;
        private final int[] aux;

        public MergeSortTask(int[] arr, int[] aux) {
            this.arr = arr;
            this.aux = aux;
        }

        @Override
        public void run() {
            mergeSort(arr, aux, 0, arr.length);
        }

        private void mergeSort(int[] arr, int[] aux, int lo, int hi) {
            if (hi - lo <= 1) {
                return;
            }

            int mid = (lo + hi) / 2;
            mergeSort(arr, aux, lo, mid);
            mergeSort(arr, aux, mid, hi);
            merge(arr, aux, lo, mid, hi);
        }

        private void merge(int[] arr, int[] aux, int lo, int mid, int hi) {
            int i = lo, j = mid, k = lo;

            while (i < mid && j < hi) {
                if (arr[i] <= arr[j]) {
                    aux[k++] = arr[i++];
                } else {
                    aux[k++] = arr[j++];
                }
            }

            while (i < mid) {
                aux[k++] = arr[i++];
            }

            while (j < hi) {
                aux[k++] = arr[j++];
            }

            System.arraycopy(aux, lo, arr, lo, hi - lo);
        }
    }
}
